﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <vector>
#include <string>
using namespace std;
// 原题连接：https://leetcode.cn/problems/palindrome-partitioning-iv/
/*
题目描述：
给你一个字符串 s ，如果可以将它分割成三个 非空 回文子字符串，那么返回 true ，否则返回 false 。

当一个字符串正着读和反着读是一模一样的，就称其为 回文字符串 。



示例 1：

输入：s = "abcbdd"
输出：true
解释："abcbdd" = "a" + "bcb" + "dd"，三个子字符串都是回文的。
示例 2：

输入：s = "bcbddxy"
输出：false
解释：s 没办法被分割成 3 个回文子字符串。


提示：

3 <= s.length <= 2000
s​​​​​​ 只包含小写英文字母。
*/

// 开始解题：
// 方法1——动态规划
class Solution {
public:
    bool checkPartitioning(string s) {
        int size = s.size();
        // 1、创建dp表
        vector<vector<bool>> dp(size, vector<bool>(size));
        // 2、初始化(省略)
        // 3、填表
        for (int i = size - 1; i >= 0; i--) {
            for (int j = i; j <= size; j++) {
                if (s[i] == s[j]) {
                    if (i == j) {
                        dp[i][j] = true;
                    }
                    else if (i + 1 == j) {
                        dp[i][j] = true;
                    }
                    else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }
            }
        }
        // 4、返回值
        for (int i = 0; i <= size - 3; i++) {
            for (int j = i + 1; j <= size - 2; j++) {
                if (dp[0][i] && dp[i + 1][j] && dp[j + 1][size - 1]) {
                    return true;
                }
            }
        }
        return false;
    }
};